Computing systems often require operations to be carried out in a secure manner. For embedded computing devices and for pervasive systems, security of operation is often crucial. To ensure operations and communications are secure, such systems employ cryptographic methods.
The implementation of such a cryptographic method must itself be secure. However, cryptographic methods are subject to attacks. One type of non-invasive attack on computing devices implementing cryptographic methods is known as a power analysis attack. A power analysis attack involves the monitoring of the power consumption of one or more components of a device while the device executes a cryptographic method.
The data derived from monitoring power consumption of the device, combined with knowledge of the operations being carried out by the device, are used to derive the secret information that is part of the cryptographic method.
One type of power analysis attack is known as a Differential Power Analysis (“DPA”) (see, for example, “Differential Power Analysis”, P. Kocher, CRYPTO'99, Lecture Notes in Computer Science, 1666, pp. 388-397, 1999, Springer-Verlag). This approach involves generating a large number of inputs by varying different bits in values to be encoded using the cryptographic method implemented in a device. The DPA attack monitors power consumption at different points in a computing device for each of these varying values and, by statistical analysis, the differential data is used to determine a likely key value for the cryptographic method (the secret information).
DPA attacks may target the input or the output of Substitution tables (also referred to as substitution boxes or “S-boxes”) that are common in cryptographic algorithms and are often implemented as look up tables. An S-box is typically indexed by a combination of key bits and plaintext. In carrying out an attack to determine a key value used in a cryptographic system, an attacker controls the plaintext values and makes guesses at the key bits. Based on these guesses, computations are performed on the acquired power traces to form a set of DPA data. The DPA data with the largest peak value is used to determine which of the key bit guesses was likely correct. As will be appreciated by those skilled in the art, another type of attack is based on electromagnetic analysis of the device carrying out a cryptographic process. Although the description below references power attacks, it will be appreciated that electromagnetic analysis attacks may raise the same issues.
There are several known countermeasures for this S-box DPA attack. Messerges (“Securing the AES Finalists Against Power Analysis Attacks”, T. Messerges, FSE 2000, Lecture Notes in Computer Science, 1978, pp. 150-164, 2001, Springer-Verlag) identifies a method of frequently regenerating tables with a different random output mask within the cryptographic algorithm. However, such an approach includes a potentially large overhead cost for each regeneration step. To improve the latency overhead required to regenerate the tables, Itoh (“DPA countermeasure based on the ‘masking method’”, K. Itoh et al. , ICICS 2001, Lecture Notes in Computer Science, 2288, pp. 440-456, 2001, Springer-Verlag) suggests using a fixed number of fixed values to mask the substitution tables. Different substitution tables may be pre-defined and the different tables used at different times in the cryptographic system. However, in the system disclosed in Itoh, the same mask is used for all round keys during each invocation of the cryptographic process. Further, there is a potential for an attacker to obtain information by using simple power analysis to identify cryptographic processes which utilize the same mask. Hence an attacker who determines one mask and has access to masked round keys (for example, through a 1st order differential power analysis), may be able to obtain all bits of the master key and all round keys. In such approaches, when the mask is determined by an attacker, the entire master key is placed at risk.
A further approach involves the duplication method described in Patarin (U.S. Pat. No. 6,658,569, Patarin et al., “Secret key cryptographic process for protecting a computer system against attacks by physical analysis”) that targets secret sharing schemes where multiple inputs to the S-box are supported. The multiple inputs to the table are transformed into a variable ν. Additionally two table outputs are produced: one is a random transformation on the input, A(ν), and another is A(ν) exclusive-or'd with S(ν). However, since the random transformation on ν does not change in the Patarin approach, there is a threat that over time an attacker may determine the random transformation used. Furthermore, since A(ν) is output from the table, there is a potential for an attacker to obtain information by using second order power analysis (using power samples of A(ν) and A(ν) exclusive-or'd with S(ν)) to obtain a correct key guess.
It is possible to implement either the Itoh or the Patarin approaches in which differing masked tables or transformations are used. However, the use of such multiple masked tables or transformations requires additional memory, power and processor resources that are not always available and the allocation of which is typically not desirable.
It would therefore be advantageous to implement substitution table masking countermeasures for resisting DPA attacks using varying table input and output masking values where such countermeasures do not require repeated table regenerations or transformation redefinition and in which different masks are used for different round keys.